package bst;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 20
 * Time:17:28
 */
//普通搜索树的定义
public class BSTree {
    public BSTNode root;

    /***
     * 1.给定key，在二叉搜索树树中进行查找
     * @param key
     * @return
     */
    public BSTNode search(long key){
        BSTNode current = root;
        while(current != null){
            if(key == current.key){
                return  current;
            }else if(key < current.key){
                current = current.left;
            }else {
                current = current.right;
            }
        }
        return  null;//表示没有找到对应的key
    }

    /***
     * 2.二叉搜索树插入节点
     * 如果插入失败（key重复了），抛出异常
     * @param key
     */
    public void insert(long key){
        BSTNode node = new BSTNode();
        node.key = key;

        if(root == null){
            root = node;
            return;
        }

        BSTNode current = node;
        BSTNode parent = null;
        while(current != null){
            if(key == current.key){
                throw new RuntimeException("插入的key值重复了。。" + key);
            }else  if(key < current.key){
                parent = current;
                current = current.left;
            }else{
                parent = current;
                current = current.right;
            }
        }
        //当current== null,parent 就是要插入的位置的父节点
        if(key < parent.key){
            parent.left = node;
        }else{
            parent.right = node;
        }
    }



}
